package com.my.code.algorithm;

/**
 * 求最小子串
 * https://leetcode-cn.com/problems/minimum-window-substring/
 */
public class MinStrLen {
    public static void main(String[] args) {
        String res = minWindow("ADOBECODEBANC", "ABC");
        System.out.println("res = " + res);
    }

    private static String minWindow(String s, String t) {
        String res = "";
        int[] window = new int[128], needs = new int[128];
        for (int i = 0; i < t.length(); i++) {
            needs[t.charAt(i)]++;
        }
        int left = 0, right = 0, count = 0, minLen = s.length();
        while (right < s.length()) {
            char ch = s.charAt(right);
            window[ch]++;
            if (needs[ch] > 0 && needs[ch] >= window[ch]) count++;
            while (count == t.length()) {
                ch = s.charAt(left);
                if (needs[ch] > 0 && needs[ch] >= window[ch]) count--;
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    res = s.substring(left, right + 1);
                }
                window[ch]--;
                left++;
            }
            right++;
        }
        return res;
    }
}
